package LeetCode._01_树;

import java.util.LinkedList;
import java.util.Queue;

public class _111_二叉树的最小深度 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int minDepth(TreeNode root) {
        if(root == null) return 0;

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        //当左子树或者右子树为空的时候，返回不为空的哪一个，因为其中有一个深度为0；否则返回深度较小的
        return root.left == null || root.right == null ? left + right + 1 : Math.min(left,right)+1;
    }

    //层序遍历
    public int minDepth2(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int minDepth = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;++i){
                TreeNode node = queue.poll();

                if(node.left == null && node.right == null) return minDepth;

                if(node.left!=null){
                    queue.offer(node.left);
                }

                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            minDepth++;
        }
        return minDepth;
    }

}
